package HashTable;

import java.util.*;

public class _594_LongestHarmoniousSubsequence {

    //using hash map
    public int findLHS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        int maxCount = 0;
        int lastCount = 0;
        int lastNum = nums[0];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.replace(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
                list.add(nums[i]);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            int tempNum = list.get(i);
            if (lastNum + 1 == tempNum) {
                int tempCount = map.get(tempNum) + lastCount;
                if (tempCount > maxCount) {
                    maxCount = tempCount;
                }
            }
            lastCount = map.get(tempNum);
            lastNum = tempNum;
        }
//        for (Map.Entry<Integer, Integer> m : map.entrySet()) {
//            if (lastNum + 1 == m.getKey()) {
//                int tempCount = m.getValue() + lastCount;
//                if (tempCount > maxCount) {
//                    maxCount = tempCount;
//                }
//            }
//            lastCount = m.getValue();
//            lastNum = m.getKey();
//        }
        return maxCount;
    }
    //wrong answer:can't deal with incontinuous situation
    public int findLHS_Wrong(int[] nums) {
        int maxCount = 0;
        int count = 0;
        int prev = nums[0], now = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == prev || nums[i] == now) {
                count++;
            } else {
                if (nums[i] == now + 1 || nums[i] ==now -1) {
                    if (prev == now) {
                        prev = now;
                        now = nums[i];
                        count++;
                    } else {
                        if (count > maxCount) {
                            maxCount = count;
                        }
                        prev = now;
                        now = nums[i];
                        count = 1;
                        int j = i-1;
                        while (j >= 0) {
                            if (nums[j] == prev) {
                                count++;
                            } else {
                                break;
                            }
                            j--;
                        }
                    }
                } else {
                    if (count > maxCount) {
                        maxCount = count;
                    }
                    count = 1;
                    prev = nums[i];
                    now = nums[i];
                }
            }
        }
        return maxCount;
    }
}
